package main

import "fmt"

type LNode struct {
	Val int
	Next *LNode
}

func CreateList(nums []int) *LNode{
	if len(nums) == 0 {
		return nil
	}
	head := &LNode{nums[0], nil}
	curr := head
	for i := 1; i < len(nums); i++ {
		curr.Next = &LNode{nums[i], nil}
		curr = curr.Next
	}
	return head
}
func (head *LNode)PrintList() {
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
	fmt.Println()
}
func Merge(head1 *LNode, head2 *LNode) *LNode{
	//第一个结点
	var head *LNode
	if head1.Val < head2.Val{
		head = head1
		head1 = head1.Next
	}else if head1.Val > head2.Val{
		head = head2
		head2 = head2.Next
	}else{
		head = head1
		head1 = head1.Next
		head2 = head2.Next
	}
	//剩下的结点
	curr := head
	for head1 != nil && head2 != nil{
		if head1.Val < head2.Val{
			curr.Next = head1
			head1 = head1.Next
			curr = curr.Next
		}else if head1.Val > head2.Val{
			curr.Next = head2
			head2 = head2.Next
			curr = curr.Next
		}else{
			curr.Next = head1
			head1 = head1.Next
			curr = curr.Next
			head2 = head2.Next
		}
	}
	for head1 != nil{
		curr.Next = head1
		head1 = head1.Next
		curr = curr.Next
	}
	for head2 != nil{
		curr.Next = head2
		head2 = head2.Next
		curr = curr.Next
	}
	return head
}
func main(){
	nums1 := []int{1, 3, 6, 7}
	nums2 := []int{2, 5, 6, 8}
	L1 := CreateList(nums1)
	L2 := CreateList(nums2)
	fmt.Println("原始链表:")
	L1.PrintList()
	L2.PrintList()
	L := Merge(L1, L2)
	fmt.Println("反转之后:")
	L.PrintList()
}